// 全排列
// 输入一个数组，要求返回数组中的n个元素，该方法会返回所有的排列
/**
 *
 * @param {*} arr 输入数组
 * @param {*} max 包含max个元素的所有数组排列
 * @returns
 */
function Arrangement(arr, max = -1) {
    // 后面实现全排列的逻辑，是按照树的生成方式来实现的。
    // 想象有N棵树，每棵树的根节点是其元素i，i的每种排列方式是从根节点到叶节点的一个唯一的组合
    // 那所有N棵树再加上所有的组合即为全排列

    // arr.sort((a, b) => a - b);

    // 限制max
    if ((max = -1)) {
        max = arr.length;
    } else {
        max = Math.min(max, arr.length);
    }

    // 打开下面代码，可以看到总共排列的个数
    // let count = arrangementCount(arr, max);
    // console.log(`input: ${JSON.stringify(arr)}, max: ${max}`);
    // console.log(`arrangementCount: ${count}`);

    let ret = []; // 用于存储所有的组合方式，一种组合记录一个

    for (let i = 0; i < arr.length; i++) {
        dfs([].concat(arr), max, i, 0, [], ret);
    }

    return ret;
}

/**
 * 计算排列数个数
 * @param {*} arr
 * @param {*} max
 * @returns
 */
function arrangementCount(arr, max) {
    let total = arr.length;
    let x = 1;
    let y = 1;

    for (let i = 0; i < max; i++) {
        x = x * (total - i);
    }

    return x / y;
}

/**
 * 返回数组arr的全排列
 * @param {*} arr 当前可用数组成的数组，排列每经过一层，都会失去一个元素
 * @param {*} max 递归总层数
 * @param {*} index 根节点index
 * @param {*} level 递归当前所处的层数
 * @param {*} acc 当前排列的数组
 * @param {*} allArrangement 存储所有的组合方式，一种组合记录一个
 * @returns
 */
function dfs(arr, max, index, level, acc, allArrangement) {
    if (acc.length == max || level === max) {
        allArrangement.push(acc);
        return;
    }

    acc.push(arr[index]);
    arr.splice(index, 1);

    // 全排列或者数组到底了
    if (arr.length === 0 && acc.length === max) {
        allArrangement.push(acc);
        return;
    }

    for (let i = 0; i < arr.length; i++) {
        dfs([].concat(arr), max, i, level + 1, [].concat(acc), allArrangement);
    }
}

module.exports = {
    Arrangement,
};

// 测试用例
var ret = Arrangement([1, 2, 3], 4);
console.table(ret);
